In storage and communication channels, data must be retrieved and transmitted reliably. In many such systems two major components protect the reliability of data: the detector and the error correcting code (ECC). The detector converts an analog waveform to a digital waveform, and then transmits the data in the digital waveform as ones and zeros. The ones and zeros are transmitted to the ECC where any erroneous bytes or symbols are corrected if the errors are within the ECC's capability.
In some such systems an information message is translated into a binary sequence. In a Reed-Solomon (RS) Encoder block, for example, the binary information sequence is segmented into sequences of m-bit symbols, where m is commonly 8 or 10. Parity symbols are added to each sequence of information symbols to form codewords. The method used to calculate the parity symbols determines the type of encoder. The output of the RS Encoder block consists of many codewords, where each n-symbol codeword consists of k information symbols and r=n−k parity symbols, forming a rate k/n code.
The channel introduces noise into the system to form the noisy sequence Y. The detector determines the most probable binary sequence {circumflex over (X)}, an estimate of X. Since noise was added to the system, with some probability, {circumflex over (X)} will contain errors. The RS decoder block uses the parity symbols to attempt to correct any symbol errors in {circumflex over (X)}. One ECC scheme is hard-decision algebraic decoding, such as provided by the Berlekamp-Massey or the Berlekamp-Welch algorithms. Either of these algorithms generally exhibits an “ECC power” of correcting t symbol errors, where t=└d/2┘ denotes the error-correcting radius (for an (n, k) RS code, the minimum distance d equals n−k+1).
The detector can use quality information from the digital waveform to detect data more accurately, but this quality information is not generally sent to the ECC (RS Decoder). A variety of “Soft-Decision ECC” schemes would allow quality (“soft”) information to be used by the ECC, thereby improving the capability of the ECC (or “extending” the ECC power). In such systems the ECC typically computes two pieces of information: error location and error magnitude. If soft information can provide the error location(s), the ECC is generally enabled to compute a larger number of the magnitudes.
One limitation of conventional Reed-Solomon ECC and similar schemes is that they correct symbols rather than bits. Even if only a single bit is in error, an entire symbol (typically 8 or 10 bits) or two of correction is used up. The ECC scheme defines a theoretical maximum on how many symbols can be corrected. Symbol erasures can be used to enlarge this theoretical maximum somewhat, generally less than double. What is needed is a way to extend further the error correction power in Reed-Solomon and similar systems.